package com.wangjie.simple;

import java.util.Arrays;
import java.util.TreeSet;

/**
 * @author jieshao
 * @date 2022/8/2 13:13
 *
 * 414. 第三大的数(给你一个非空数组，返回此数组中第三大的数 。如果不存在，则返回数组中最大的数)
 */
public class Test19 {
    public static void main(String[] args) {
        int[] arr = {2, 1, 2, 3, 10, 3, 5, 5, 10};
        System.out.println(Arrays.toString(arr));
        sort(arr);
        System.out.println(Arrays.toString(arr));
        int result1 = thirdMax1(arr);
        System.out.println(result1);

        int result2 = thirdMax2(arr);
        System.out.println(result2);
    }

    public static int thirdMax1(int[] nums) {
        sort(nums);
        int diff = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1] && ++diff == 3) {
                return nums[i];
            }
        }
        return nums[0];
    }

    public static int thirdMax2(int[] nums) {
        TreeSet<Integer> s = new TreeSet<>();
        for (int num : nums) {
            s.add(num);
            if (s.size() > 3) {
                s.remove(s.first());
            }
        }
        return s.size() == 3 ? s.first() : s.last();
    }

    public int thirdMax3(int[] nums) {
        long a = Long.MIN_VALUE, b = Long.MIN_VALUE, c = Long.MIN_VALUE;
        for (long num : nums) {
            if (num > a) {
                c = b;
                b = a;
                a = num;
            } else if (a > num && num > b) {
                c = b;
                b = num;
            } else if (b > num && num > c) {
                c = num;
            }
        }
        return c == Long.MIN_VALUE ? (int) a : (int) c;
    }

    public int thirdMax4(int[] nums) {
        Integer a = null, b = null, c = null;
        for (int num : nums) {
            if (a == null || num > a) {
                c = b;
                b = a;
                a = num;
            } else if (a > num && (b == null || num > b)) {
                c = b;
                b = num;
            } else if (b != null && b > num && (c == null || num > c)) {
                c = num;
            }
        }
        return c == null ? a : c;
    }

    public static void sort(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = 0; j < nums.length - 1 - i; j++) {
                if (nums[j + 1] > nums[j]) {
                    int t = nums[j + 1];
                    nums[j + 1] = nums[j];
                    nums[j] = t;
                }
            }
        }
    }
}